﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Security.Cryptography;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

/// <summary>
/// http://codekata.com/kata/kata05-bloom-filters/
/// </summary>
namespace RandomKatas.Kata05
{
    public class Md5Hasher<T>
    {
        public Md5Hasher()
        {
            this.md5 = MD5.Create();
        }

        public IEnumerable<Func<T, int>> GetHashers(int numHashers)
        {
            for (int i = 0; i < numHashers; ++i)
            {
                yield return t =>
                {
                    var offset = i * 5;
                    return Hash(t, offset);
                };
            }
        }

        private int Hash(T value, int offset)
        {
            byte[] hash = null;
            if (latestHash == null || !object.ReferenceEquals(latestHash.Item1, value))
            {
                hash = md5.ComputeHash(Encoding.UTF8.GetBytes(value.ToString()));
                latestHash = Tuple.Create(value, hash);
            }
            else
                hash = latestHash.Item2;

            return Math.Abs(BitConverter.ToInt32(hash, offset % (hash.Length - 4)));
        }

        private Tuple<T, byte[]> latestHash;
        private MD5 md5;
    }

    public class BloomFilter<T>
    {
        public static BloomFilter<T> FromMd5(int bitsetSize, int numHashes)
        {
            var md5Gen = new Md5Hasher<T>();
            var hashes = md5Gen.GetHashers(numHashes);
            return new BloomFilter<T>(bitsetSize, hashes);
        }

        public BloomFilter(int bitsetSize, IEnumerable<Func<T, int>> hashFuncs)
        {
            this.bitset = new BitArray(bitsetSize);
            this.hashes = new List<Func<T, int>>(hashFuncs);
        }

        public void AddItem(T item)
        {
            foreach (var hash in this.hashes)
            {
                var idx = hash(item) % bitset.Length;
                bitset[idx] = true;
            }
        }

        public bool IsInSet(T item)
        {
            foreach (var hash in this.hashes)
            {
                var idx = hash(item) % bitset.Length;
                if (!bitset[idx]) return false;
            }

            return true;
        }

        private BitArray bitset;
        private List<Func<T, int>> hashes;
    }
}
